use std::collections::HashMap;

pub fn dp_rec_mc(amount: u32) -> u32 {
    // TODO: 这里写逻辑
    let denominations = [100, 50, 30, 20, 10, 5, 2, 1];
    let mut cache = HashMap::new();
    dp_rec_mc_helper(amount, &denominations, &mut cache)
}

fn dp_rec_mc_helper(amount: u32, denominations: &[u32], cache: &mut HashMap<u32, u32>) -> u32 {
    if amount == 0 {
        return 0;
    }
    // 如果缓存中已经有结果，直接返回
    if let Some(&result) = cache.get(&amount) {
        return result;
    }

    let mut min_coins = std::u32::MAX;
    for &coin in denominations {
        if amount >= coin {
            let sub_min_coins = 1 + dp_rec_mc_helper(amount - coin, denominations, cache);
            min_coins = min_coins.min(sub_min_coins);
        }
    }
    // 将结果存入缓存
    cache.insert(amount, min_coins);
    min_coins
}